package 背包问题;

import org.junit.Test;

/**
 * @Classname OnePackage2
 * @Description 背包问题的算法优化
 * @Date 2022/3/25 16:32
 * @Created by xjl
 */
public class OnePackage2 {

    private int OnePackage(int[] v, int[] w, int k, int c) {
        int[] Results = new int[c + 1];
        // 开始填表 倒着填写表格数据
        for (int m = 0; m < v.length; m++) {
            for (int n = c; n >= w[m]; n--) {
                Results[n] = Math.max(Results[n], Results[n - w[m]] + v[m]);
            }
        }
        return Results[Results.length - 1];
    }

    @Test
    public void TestOnePackage() {
        int[] v = {0, 2, 4, 3, 7};
        int[] w = {0, 2, 3, 5, 5};
        int k = 4;
        int c = 10;
        int result = OnePackage(v, w, k, c);
        System.out.println(result);
    }
}
